/**
 * 版权所有 (C), 2019-2019, XXX有限公司
 * 项目名：com.company.study.dsa.linkedlist
 * 文件名: SingleLinkedList
 * 日期: 2019/6/18 14:08
 * 说明:
 */
package com.company.study.dsa.linkedlist;

/**
 * 单向链表
 *
 * @author Anbang713
 * @create 2019/6/18
 */
public class SingleLinkedList {

    /**
     * 链表中节点的个数，也就是链表的长度或大小
     */
    private int size;
    /**
     * 头节点
     */
    private Node head;

    public SingleLinkedList() {
        size = 0;
        head = null;
    }

    /**
     * 在链表的表头添加节点
     *
     * @param data 新增节点的数据元素
     * @return 新表头的数据元素
     */
    public Object addHead(Object data) {
        Node newHead = new Node(data);
        if (isEmpty() == false) {
            newHead.next = head;
        }
        head = newHead;
        size++;
        return data;
    }

    /**
     * 删除表头节点
     *
     * @return 被删除表头节点的数据元素
     */
    public Object deleteHead() {
        if (isEmpty()) {
            return null;
        }
        Object data = head.data;
        head = head.next;
        size--;
        return data;
    }

    /**
     * 查找数据元素等于data的节点，找不到则返回null
     *
     * @param data 待查找的数据元素
     * @return
     */
    public Node find(Object data) {
        Node current = head;
        int tempSize = size;
        while (tempSize > 0) {
            if (data.equals(current.data)) {
                return current;
            }
            current = current.next;
            tempSize--;
        }
        return null;
    }

    /**
     * 删除指定数据元素的节点
     *
     * @param data 待删除节点的数据元素
     * @return true表示成功删除，false表示删除失败
     */
    public boolean delete(Object data) {
        if (isEmpty()) {
            return false;
        }
        Node current = head;
        Node previous = head;
        while (current.data.equals(data) == false) {
            if (current.next == null) {
                return false;
            }
            previous = current;
            current = current.next;
        }
        //如果删除的是第一个节点
        if (current.equals(head)) {
            deleteHead();
        } else {
            //删除的节点不是第一个节点
            previous.next = current.next;
            size--;
        }
        return true;
    }

    /**
     * 显示节点信息
     */
    public void display() {
        if (isEmpty() == false) {
            Node node = head;
            int tempSize = size;
            if (tempSize == 1) {//当前链表只有一个节点
                System.out.println("[" + node.data + "]");
                return;
            }
            while (tempSize > 0) {
                if (node.equals(head)) {
                    System.out.print("[" + node.data + "->");
                } else if (node.next == null) {
                    System.out.print(node.data + "]");
                } else {
                    System.out.print(node.data + "->");
                }
                node = node.next;
                tempSize--;
            }
            System.out.println();
        } else {
            System.out.println("[]");
        }
    }

    /**
     * 判断链表是否为空
     *
     * @return
     */
    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * 链表中的节点类
     */
    private class Node {
        /**
         * 节点的数据元素
         */
        private Object data;
        /**
         * 每个节点指向下一个节点的连接
         */
        private Node next;

        public Node(Object data) {
            this.data = data;
        }
    }
}